package com.algorithm.example.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <p>
 * <h2>树节点</h2>
 * </p>
 *
 * @author lzt
 * @version 1.0
 * @since 2024/1/24 22:16
 */
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return String.valueOf(this.val);
    }

    /**
     * 前序遍历 - 递归
     *
     * @param node - 节点
     */
    static void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + "\t");
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 前序遍历 - 非递归
     */
    public static void preOrder1(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                System.out.print(curr.val + "\t");
                curr = curr.left;
            } else {
                TreeNode pop = stack.pop();
                curr = pop.right;
            }
        }

    }

    /**
     * 中序遍历
     *
     * @param node - 节点
     */
    static void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.out.print(node.val + "\t");
        inOrder(node.right);
    }

    /**
     * 中序遍历 - 非递归
     *
     * @param root - 根节点
     */
    public static void inOrder1(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode pop = stack.pop();
                System.out.print(pop.val + "\t");
                curr = pop.right;

            }
        }
    }

    /**
     * 后序遍历
     *
     * @param node - 节点
     */
    static void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val + "\t");
    }

    /**
     * 后序遍历 - 非递归
     *
     * @param root - 根节点
     */
    public static void postOrder1(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;
        TreeNode pop = null;

        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;

            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                    System.out.print(pop.val + "\t");
                } else {
                    curr = peek.right;
                }
            }
        }
    }

    /**
     * 最大深度 - 递归
     *
     * @param node - 根节点
     */
    public static int maxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int a = maxDepth(node.left);
        int b = maxDepth(node.right);
        if (a == 0 || b == 0) {
            return a + b + 1;
        }
        return Integer.max(a, b) + 1;
    }

    /**
     * 最小深度 - 非递归 -> 层序遍历
     *
     * @param root - 根节点
     * @return - 深度
     */
    public static int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int a = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            a++;
            int size = queue.size();
            for (int i = 0; i <size; i++) {
                TreeNode poll = queue.poll();
                if(poll.left == null && poll.right == null) {
                    return a;
                }
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }

        }
        return a;

    }


    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(
                1,
                new TreeNode(2,
                        new TreeNode(4),
                        new TreeNode(5)),
                new TreeNode(3,
                        new TreeNode(6),
                        new TreeNode(7,
                                new TreeNode(8,
                                        new TreeNode(9), null)
                                , null
                        ))
        );

        preOrder(treeNode);
        System.out.println("前序遍历-递归");
        inOrder(treeNode);
        System.out.println("中序遍历-递归");
        postOrder(treeNode);
        System.out.println("后序遍历-递归");
        preOrder1(treeNode);
        System.out.println("前序遍历-非递归");
        inOrder1(treeNode);
        System.out.println("中序遍历-非递归");
        postOrder1(treeNode);
        System.out.println("后序遍历-非递归");
        System.out.println("最大深度" + maxDepth(treeNode));
        System.out.println("最大深度" + minDepth(treeNode));


    }
}
